package pers.qianyu.month_202012.date_20201224;

import java.util.*;

/**
 * 871. 最低加油次数
 * https://leetcode-cn.com/problems/minimum-number-of-refueling-stops/
 *
 * @author mizzle rain
 * @date 2020-12-24 22:21
 */
public class MinRefuelStops {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int len = stations.length;
        if (len == 0) {
            return target <= startFuel ? 0 : -1;
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);
        // pre 记录上一次的坐标，用于计算路径长度
        int count = 0, pre = 0;
        for (int[] station : stations) {
            int distance = station[0] - pre;
            pre = station[0];
            int gas = station[1];
            while (!q.isEmpty() && startFuel < distance) {
                // 以现在的油量走不过去
                startFuel += q.poll();
                count++;
            }
            // 如果加了所有的油，还是过不去，就直接返回 -1
            if (startFuel < distance) {
                return -1;
            }
            q.offer(gas);
            startFuel -= distance;
            target -= distance;
        }
        // 走完所有加油站，还没有走到目的地
        while (!q.isEmpty() && startFuel < target) {
            startFuel += q.poll();
            count++;
        }
        if (q.isEmpty() && startFuel < target) {
            return -1;
        }
        return count;
    }
}
